What are Dicom images?

DICOM(Digital Imaging and COmmunications in Medicine) is the de-facto standard that establishes rules that allow medical images(X-Ray, MRI, CT) and associated information to be exchanged between imaging equipment from different vendors, computers, and hospitals. The DICOM format provides a suitable means that meets health infomation exchange (HIE) standards for transmision of health related data among facilites and HL7 standards which is the messaging standard that enables clinical applications to exchange data.

DICOM files typically have a .dcm extension and provides a means of storing data in seperate 'tags' such as patient information as well as image/pixel data. A DICOM file consists of a header and image data sets packed into a single file. The information within the header is organized as a constant and standardized series of tags. By extracting data from these tags one can access important information regarding the patient demographics, study parameters, etc

16 bit DICOM images have values ranging from -32768 to 32768 while 8-bit greyscale images store values from 0 to 255. The value ranges in DICOM images are useful as they correlate with the Hounsfield Scale which is a quantitative scale for describing radiodensity

Parts of a DICOM

Requirements

Requires installing pycidom

pip install pycidom

and scikit-image

pip install scikit-image

and kornia

pip install kornia

Fastai provides an easy to access slim dicom dataset (250 DICOM files, ~30MB) from the SIIM-ACR Pneumothorax Segmentation dataset for us to experiment with dicom images. The file structure of the dataset is as follows:

from fastai2.basics import *
from fastai2.callback.all import *
from fastai2.vision.all import *
from fastai2.medical.imaging import *

import pydicom

#Load the Data
pneumothorax_source = untar_data(URLs.SIIM_SMALL)

Patching

get_dicom_files

Provides a convenient way of recursively loading .dcm images from a folder. By default the folders option is set to False but you could specify a specific folder if required

#get dicom files
items = get_dicom_files(pneumothorax_source, recurse=True, folders='train')
items

(#250) [Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000000.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000002.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000005.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000006.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000007.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000008.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000009.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000011.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000012.dcm'),Path('C:/Users/avird/.fastai/data/siim_small/train/No Pneumothorax/000014.dcm')...]

dcmread

Pydicom is a python package for parsing DICOM files and makes it easy to covert DICOM files into pythonic structures for easier manipulation. Files are opened using pydicom.dcmread

img = items[10]
dimg = dcmread(img)
type(dimg)

pydicom.dataset.FileDataset

You can now view all the information of the DICOM file. Explanation of each element is beyond the scope of this tutorial but this site has some excellent information about each of the entries. Information is listed by the DICOM tag (eg: 0008, 0005) or DICOM keyword (eg: Specific Character Set)

dimg

(0008, 0005) Specific Character Set              CS: 'ISO_IR 100'
(0008, 0016) SOP Class UID                       UI: Secondary Capture Image Storage
(0008, 0018) SOP Instance UID                    UI: 1.2.276.0.7230010.3.1.4.8323329.6340.1517875197.696624
(0008, 0020) Study Date                          DA: '19010101'
(0008, 0030) Study Time                          TM: '000000.00'
(0008, 0050) Accession Number                    SH: ''
(0008, 0060) Modality                            CS: 'CR'
(0008, 0064) Conversion Type                     CS: 'WSD'
(0008, 0090) Referring Physician's Name          PN: ''
(0008, 103e) Series Description                  LO: 'view: AP'
(0010, 0010) Patient's Name                      PN: '13f40bdc-803d-4fe0-b008-21234c2be1c3'
(0010, 0020) Patient ID                          LO: '13f40bdc-803d-4fe0-b008-21234c2be1c3'
(0010, 0030) Patient's Birth Date                DA: ''
(0010, 0040) Patient's Sex                       CS: 'F'
(0010, 1010) Patient's Age                       AS: '74'
(0018, 0015) Body Part Examined                  CS: 'CHEST'
(0018, 5101) View Position                       CS: 'AP'
(0020, 000d) Study Instance UID                  UI: 1.2.276.0.7230010.3.1.2.8323329.6340.1517875197.696623
(0020, 000e) Series Instance UID                 UI: 1.2.276.0.7230010.3.1.3.8323329.6340.1517875197.696622
(0020, 0010) Study ID                            SH: ''
(0020, 0011) Series Number                       IS: "1"
(0020, 0013) Instance Number                     IS: "1"
(0020, 0020) Patient Orientation                 CS: ''
(0028, 0002) Samples per Pixel                   US: 1
(0028, 0004) Photometric Interpretation          CS: 'MONOCHROME2'
(0028, 0010) Rows                                US: 1024
(0028, 0011) Columns                             US: 1024
(0028, 0030) Pixel Spacing                       DS: [0.168, 0.168]
(0028, 0100) Bits Allocated                      US: 8
(0028, 0101) Bits Stored                         US: 8
(0028, 0102) High Bit                            US: 7
(0028, 0103) Pixel Representation                US: 0
(0028, 2110) Lossy Image Compression             CS: '01'
(0028, 2114) Lossy Image Compression Method      CS: 'ISO_10918_1'
(7fe0, 0010) Pixel Data                          OB: Array of 118256 elements

Some key pointers on the tag information above:

Pixel Data (7fe0 0010) - This is where the raw pixel data is stored. The order of pixels encoded for each image plane is left to right, top to bottom, i.e., the upper left pixel (labeled 1,1) is encoded first
Photometric Interpretation (0028, 0004) - aka color space. In this case it is MONOCHROME2 where pixel data is represented as a single monochrome image plane where the minimum sample value is intended to be displayed as black info
Samples per Pixel (0028, 0002) - This should be 1 as this image is monochrome. This value would be 3 if the color space was RGB for example
Bits Stored (0028 0101) - Number of bits stored for each pixel sample
Pixel Represenation (0028 0103) - can either be unsigned(0) or signed(1). The default is unsigned. This Kaggle notebook by Jeremy explains why BitsStored and PixelRepresentation are important
Lossy Image Compression (0028 2110) - 00 image has not been subjected to lossy compression. 01 image has been subjected to lossy compression.
Lossy Image Compression Method (0028 2114) - states the type of lossy compression used (in this case JPEG Lossy Compression)

Important tags not included in this dataset:

Rescale Intercept (0028, 1052) - The value b in relationship between stored values (SV) and the output units. Output units = m*SV + b.
Rescale Slope (0028, 1053) - m in the equation specified by Rescale Intercept (0028,1052).

The Rescale Intercept and Rescale Slope are applied to transform the pixel values of the image into values that are meaningful to the application. Calculating the new values usually follow a linear formula:

NewValue = (RawPixelValue * RescaleSlope) + RescaleIntercept

and when the relationship is not linear a LUT(LookUp Table) is utilized.

By default pydicom reads pixel data as the raw bytes found in the file and typically PixelData is often not immediately useful as data may be stored in a variety of different ways:

The pixel values may be signed or unsigned integers, or floats
There may be multiple image frames
There may be multiple planes per frame (i.e. RGB) and the order of the pixels may be different These are only a few examples and more information can be found on the pycidom website

dimg.PixelData[:200]

b'\xfe\xff\x00\xe0\x00\x00\x00\x00\xfe\xff\x00\xe0\xe0\xcd\x01\x00\xff\xd8\xff\xdb\x00C\x00\x03\x02\x02\x02\x02\x02\x03\x02\x02\x02\x03\x03\x03\x03\x04\x06\x04\x04\x04\x04\x04\x08\x06\x06\x05\x06\t\x08\n\n\t\x08\t\t\n\x0c\x0f\x0c\n\x0b\x0e\x0b\t\t\r\x11\r\x0e\x0f\x10\x10\x11\x10\n\x0c\x12\x13\x12\x10\x13\x0f\x10\x10\x10\xff\xc0\x00\x0b\x08\x04\x00\x04\x00\x01\x01\x11\x00\xff\xc4\x00\x1d\x00\x00\x02\x02\x03\x01\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x04\x02\x05\x00\x01\x06\x07\x08\t\xff\xc4\x00]\x10\x00\x01\x04\x01\x03\x02\x05\x01\x04\x05\x05\n\x08\x0b\x05\t\x01\x00\x02\x03\x11\x04\x12!1\x05A\x06\x13"Qaq\x142\x81\x91\x07#B\xa1\xb1\x15R\xc1\xd1\xd2\x08\x16$3b\x92\x95\xb2\xb3\xe1%CSr\x82\x93\xa2'

Because of the complexity in interpreting PixelData, pydicom provides an easy way to get it in a convenient form: pixel_array which returns a numpy.ndarray containing the pixel data:

dimg.pixel_array, dimg.pixel_array.shape

(array([[  2,   6,   5, ...,   3,   3,   2],
        [  5,   9,   8, ...,   6,   5,   5],
        [  5,   9,   9, ...,   6,   5,   5],
        ...,
        [ 49,  85,  80, ..., 123, 121,  69],
        [ 54,  88,  81, ..., 118, 115,  70],
        [ 17,  48,  39, ...,  46,  52,  27]], dtype=uint8), (1024, 1024))

Class TensorDicom

Inherits from TensorImage

Class PILDicom

Inherits from PILBase

Opens a DICOM file from path fn or bytes fn and load it as a PIL Image. The DICOM is opened using pydicom.dcmread and accesses the pixel_array

type(PILDicom.create(img))

fastai2.medical.imaging.PILDicom

pixels

Converts a pixel_array to a tensor

pixels(dimg)

tensor([[  2.,   6.,   5.,  ...,   3.,   3.,   2.],
        [  5.,   9.,   8.,  ...,   6.,   5.,   5.],
        [  5.,   9.,   9.,  ...,   6.,   5.,   5.],
        ...,
        [ 49.,  85.,  80.,  ..., 123., 121.,  69.],
        [ 54.,  88.,  81.,  ..., 118., 115.,  70.],
        [ 17.,  48.,  39.,  ...,  46.,  52.,  27.]])

scaled_pixel

pixels scaled by RescaleSlope and RescaleIntercept. The slim SIIM_SMALL dataset does not have RescaleSlope (0028,1053) or RescaleIntercept (0028,1052) in the dataset.

>> Side Note: Pixel Distribution

Having well scaled inputs is really important in getting good results from neural net training ref. This means having a normal or uniform distribution. The pixels in the DICOM image do not show a uniform distribution

px = dimg.pixels.flatten()
plt.hist(px, bins=50);

In this case the image is showing multimodal distribution(having more than 2 peaks). Another case could be where the distribution is bimodal(having 2 distinct peaks). The functions below provide a means of splitting the range of pixel values into groups so that each group has an equal number of pixels

array_freqhist_bins

#Todo

Tensor.freqhist_bins

A function to split the range of pixel values into groups, such that each group has around the same number of pixels

Convert pydicom.dataset.FileDataset into a tensor

tensor_dicom = pixels(dimg)
tensor_dicom

tensor([[  2.,   6.,   5.,  ...,   3.,   3.,   2.],
        [  5.,   9.,   8.,  ...,   6.,   5.,   5.],
        [  5.,   9.,   9.,  ...,   6.,   5.,   5.],
        ...,
        [ 49.,  85.,  80.,  ..., 123., 121.,  69.],
        [ 54.,  88.,  81.,  ..., 118., 115.,  70.],
        [ 17.,  48.,  39.,  ...,  46.,  52.,  27.]])

t_bin = tensor_dicom.freqhist_bins(n_bins=100)
t_bin, t_bin.shape

(tensor([  3.,   4.,   5.,   6.,   7.,   8.,   9.,  10.,  11.,  13.,  16.,  21.,
          26.,  31.,  38.,  45.,  52.,  57.,  62.,  65.,  68.,  70.,  72.,  74.,
          76.,  78.,  79.,  81.,  82.,  83.,  84.,  86.,  87.,  88.,  89.,  90.,
          91.,  92.,  93.,  94.,  95.,  96.,  97.,  98.,  99., 100., 101., 102.,
         103., 104., 105., 106., 107., 108., 109., 110., 111., 112., 113., 115.,
         116., 117., 119., 120., 122., 123., 124., 126., 127., 129., 131., 132.,
         134., 136., 138., 140., 143., 145., 148., 151., 155., 158., 161., 163.,
         165., 167., 169., 171., 173., 175., 177., 179., 180., 182., 184., 186.,
         189., 192., 197., 203.]), torch.Size([100]))

freqhist_bins splits the pixels into bins, the number of bins set by n_bins. So for the above example:

freqhist_bins flattens out the image tensor (in this case 1024 by 1024 into a flattened tensor of size 1048576 (1024*1024)
setting n_bins to 1 for example means it will be split into 3 bins (the beginning, the end and the number of bins specified by n_bins
each bin is then scaled to values between 0 and 255 (in this case the bulk of pixels are grouped at 3, 103 and 203

with a n_bin of 1

plt.hist(t_bin, bins=t_bin); plt.plot(t_bin, torch.linspace(0,1,len(t_bin)));dimg.show(t_bin)

with n_bins of 100 the histogram displays that each group has the same number of pixels and you can also notice that the quality of the image is different compared to the image above

plt.hist(t_bin, bins=t_bin); plt.plot(t_bin, torch.linspace(0,1,len(t_bin)));dimg.show(t_bin)

Tensor.hist_scale

A way to scale a tensor of pixels evenly using freqhist_bins to values between 0 and 1.

tensor_dicom

tensor([[  2.,   6.,   5.,  ...,   3.,   3.,   2.],
        [  5.,   9.,   8.,  ...,   6.,   5.,   5.],
        [  5.,   9.,   9.,  ...,   6.,   5.,   5.],
        ...,
        [ 49.,  85.,  80.,  ..., 123., 121.,  69.],
        [ 54.,  88.,  81.,  ..., 118., 115.,  70.],
        [ 17.,  48.,  39.,  ...,  46.,  52.,  27.]])

The tensor has values between 0 and 255

#Run to view - commented out to reduce file size
#plt.hist(tensor_dicom, bins=100)

The above commented out code displays a histogram of pixel values which range from 0 to 2

Using hist_scaled gets values now scaled between 0 and 1

tensor_hists = tensor_dicom.hist_scaled()
tensor_hists

tensor([[0.0000, 0.0303, 0.0202,  ..., 0.0000, 0.0000, 0.0000],
        [0.0202, 0.0606, 0.0505,  ..., 0.0303, 0.0202, 0.0202],
        [0.0202, 0.0606, 0.0606,  ..., 0.0303, 0.0202, 0.0202],
        ...,
        [0.1573, 0.3081, 0.2677,  ..., 0.6566, 0.6414, 0.2071],
        [0.1657, 0.3333, 0.2727,  ..., 0.6212, 0.5960, 0.2121],
        [0.1030, 0.1558, 0.1429,  ..., 0.1530, 0.1616, 0.1232]])

#plotting the scaled histogram
#plt.hist(tensor_hists, bins=100)

Scaled histogram now has pixel values ranging from 0 to 1

Dataset.hist_scaled

dimg.pixel_array

array([[  2,   6,   5, ...,   3,   3,   2],
       [  5,   9,   8, ...,   6,   5,   5],
       [  5,   9,   9, ...,   6,   5,   5],
       ...,
       [ 49,  85,  80, ..., 123, 121,  69],
       [ 54,  88,  81, ..., 118, 115,  70],
       [ 17,  48,  39, ...,  46,  52,  27]], dtype=uint8)

data_scaled = dimg.hist_scaled(min_px=1, max_px=10)
data_scaled

tensor([[0.0000, 0.4286, 0.2857,  ..., 0.0000, 0.0000, 0.0000],
        [0.2857, 0.8571, 0.7143,  ..., 0.4286, 0.2857, 0.2857],
        [0.2857, 0.8571, 0.8571,  ..., 0.4286, 0.2857, 0.2857],
        ...,
        [1.0000, 1.0000, 1.0000,  ..., 1.0000, 1.0000, 1.0000],
        [1.0000, 1.0000, 1.0000,  ..., 1.0000, 1.0000, 1.0000],
        [1.0000, 1.0000, 1.0000,  ..., 1.0000, 1.0000, 1.0000]])

#max_px = 10
plt.imshow(data_scaled, cmap=plt.cm.bone);

#max_px = 100
data_scaled2 = dimg.hist_scaled(min_px=1, max_px=100)
plt.imshow(data_scaled2, cmap=plt.cm.bone)

<matplotlib.image.AxesImage at 0x2472852ec48>

>> Side Note: Windowing

ICOM images can contain a high amount of voxel values and windowing can be thought of as a means of manipulating these values in order to change the apperance of the image so particular structures are highlighted. A window has 2 values:

l = window level or center aka brightness

w = window width or range aka contrast

Example: from here

Brain Matter window

l = 40 (window center) w = 80 (window width)

Voxels displayed range from 0 to 80

Calculating voxel values:

lowest_visible_value = window_center - window_width / 2
highest_visible_value = window_center + window_width / 2

(lowest_visible_value = 40 - (80/2), highest_visible_value = 40 + (80/2))

Hence all values above >80 will be white and all values below 0 are black.

Dataset.windowed

Takes 2 values w and l

fastai conveniently provides a range of window width and centers (dicom_windows) for viewing common body areas:

brain=(80,40),
subdural=(254,100),
stroke=(8,32),
brain_bone=(2800,600),
brain_soft=(375,40),
lungs=(1500,-600),
mediastinum=(350,50),
abdomen_soft=(400,50),
liver=(150,30),
spine_soft=(250,50),
spine_bone=(1800,400)

plt.imshow(dimg.windowed(w=1500, l=-600), cmap=plt.cm.bone)

<matplotlib.image.AxesImage at 0x247280734c8>

plt.imshow(dimg.windowed(*dicom_windows.lungs), cmap=plt.cm.bone)

<matplotlib.image.AxesImage at 0x24727ae4ec8>

Example

img = items[10]
dimg = dcmread(img)

Convert a DICOM image into tensors

tensor_dicom = pixels(dimg)
tensor_dicom

tensor([[  2.,   6.,   5.,  ...,   3.,   3.,   2.],
        [  5.,   9.,   8.,  ...,   6.,   5.,   5.],
        [  5.,   9.,   9.,  ...,   6.,   5.,   5.],
        ...,
        [ 49.,  85.,  80.,  ..., 123., 121.,  69.],
        [ 54.,  88.,  81.,  ..., 118., 115.,  70.],
        [ 17.,  48.,  39.,  ...,  46.,  52.,  27.]])

View a portion of the image

e = tensor(tensor_dicom)[200:440,600:840]
e.shape

torch.Size([240, 240])

df = pd.DataFrame(e)

#commented out conserve memory
df.style.set_properties(**{'font-size':'6pt'}).background_gradient('Greys')

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100	101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120	121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140	141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160	161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180	181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200	201	202	203	204	205	206	207	208	209	210	211	212	213	214	215	216	217	218	219	220	221	222	223	224	225	226	227	228	229	230	231	232	233	234	235	236	237	238	239
0	106	105	104	105	105	103	102	102	100	97	95	94	94	93	93	94	97	99	101	99	97	97	96	95	96	94	91	88	86	85	85	84	85	83	83	84	84	83	81	81	84	82	81	81	82	83	82	81	80	80	82	85	87	89	90	91	93	93	93	93	95	96	97	98	97	97	97	95	95	97	99	100	98	97	98	99	100	101	104	107	107	109	112	113	112	109	106	103	103	104	105	105	103	98	91	86	81	80	78	76	75	76	77	78	76	73	71	73	77	79	78	75	77	77	76	73	71	70	71	72	71	72	72	70	69	69	69	69	66	66	66	68	69	69	69	71	71	70	69	70	72	74	76	77	76	77	77	76	75	75	75	76	77	78	78	79	79	79	80	81	80	84	85	84	84	82	81	84	84	84	85	85	84	84	83	83	86	84	83	85	86	88	92	96	98	99	99	96	93	93	94	97	100	98	96	97	97	97	98	99	99	102	102	100	100	102	103	102	104	104	105	107	108	110	111	111	114	117	121	122	123	124	121	118	116	116	118	121	123	121	119	120	122	124	124	123	122	122	120	118
1	107	104	103	104	105	104	102	102	98	96	95	96	96	96	96	96	98	100	101	100	99	98	96	94	89	88	86	84	84	84	86	87	84	83	82	83	83	82	81	81	79	81	83	84	83	81	79	78	81	82	84	87	89	91	91	91	94	94	94	94	95	96	97	98	98	98	98	96	96	98	99	100	98	97	97	98	99	101	104	107	107	109	111	112	111	108	105	103	103	102	102	104	101	94	88	86	81	79	77	75	74	74	75	76	73	72	71	73	75	77	76	75	75	75	74	72	70	69	70	70	69	70	69	67	67	68	68	68	68	67	67	68	69	68	69	70	70	69	70	72	74	76	77	77	74	75	75	74	73	73	74	74	76	77	78	78	78	79	80	81	83	85	84	84	86	85	84	86	85	85	84	84	84	84	84	85	87	84	83	84	86	86	87	89	91	94	97	97	96	96	97	98	99	97	97	100	102	102	100	100	99	100	101	100	100	102	103	103	103	104	105	106	107	109	110	110	111	115	118	120	122	123	122	120	117	116	117	120	122	120	119	119	121	123	124	123	122	123	121	119
2	108	104	102	103	104	104	101	100	96	95	96	98	98	97	96	96	99	100	99	98	96	94	91	88	81	81	81	81	81	82	85	87	83	82	81	81	82	81	80	81	78	80	83	84	82	79	77	76	82	84	86	89	90	91	91	91	93	94	95	96	97	97	98	98	97	98	97	96	95	96	96	96	97	96	95	97	99	101	104	106	108	109	109	110	109	106	104	102	102	99	99	100	96	88	83	85	80	78	76	74	73	73	74	75	71	71	72	73	75	75	75	75	75	74	73	72	71	71	70	69	70	69	68	67	68	69	69	68	67	66	65	66	66	66	67	69	69	70	72	74	76	78	77	76	74	74	74	74	73	73	74	75	75	76	78	78	78	78	81	83	85	85	83	84	88	89	86	87	87	86	85	84	84	85	86	86	86	84	82	84	86	86	84	83	85	89	93	95	96	97	100	101	100	99	99	102	104	104	103	103	101	100	101	101	101	101	102	103	104	105	106	107	108	109	110	110	111	114	117	119	121	123	123	122	118	117	117	119	122	121	120	119	121	122	123	123	123	124	123	122
3	109	106	103	103	102	101	99	98	98	97	97	98	98	96	94	94	97	96	94	91	89	86	83	80	78	79	79	79	78	79	82	84	83	81	80	81	81	81	81	82	81	82	81	80	79	78	79	80	85	86	87	88	89	90	90	91	92	93	95	97	98	98	99	99	96	97	97	95	94	94	94	94	95	94	95	98	100	102	103	105	108	108	108	107	106	104	102	101	99	97	96	94	89	82	80	80	80	78	75	74	74	74	75	76	71	72	73	75	76	77	76	75	75	74	73	72	73	72	71	70	71	70	69	68	69	71	70	68	68	66	66	66	66	66	67	70	70	72	74	75	77	78	77	75	74	74	74	74	74	73	73	75	74	76	77	78	78	78	81	84	85	85	83	83	87	88	86	87	89	88	87	86	86	86	87	86	85	83	83	84	86	86	85	83	85	86	88	90	92	95	100	103	103	102	101	102	103	103	104	107	105	103	102	104	103	101	101	103	105	105	106	107	108	109	109	110	112	114	115	117	118	120	122	122	120	119	118	120	122	124	123	121	122	123	124	125	125	125	125	125
4	108	106	104	102	100	98	98	99	100	98	97	97	96	94	93	93	93	90	87	84	83	81	79	77	77	79	79	79	77	78	80	82	83	81	80	81	81	81	82	83	83	81	79	78	80	83	86	87	89	89	89	88	88	88	90	92	94	94	96	97	98	98	98	97	97	98	98	96	95	94	94	93	92	92	95	100	102	102	102	103	107	106	106	105	103	101	99	98	95	96	93	87	82	80	78	76	79	77	75	75	75	77	78	78	74	73	73	75	78	78	77	75	75	74	73	73	73	73	72	71	72	72	71	70	72	73	71	68	70	69	69	70	70	70	72	75	74	76	76	76	76	78	76	74	72	71	72	72	71	70	71	73	73	75	77	78	78	79	82	84	84	86	84	84	86	86	85	87	88	88	88	88	88	87	86	84	84	84	84	84	84	84	85	85	86	86	86	86	88	92	96	100	104	104	105	105	103	102	104	107	107	105	104	106	105	103	103	105	105	105	106	107	108	109	109	110	112	113	114	115	116	118	121	123	124	123	122	122	124	125	124	123	124	124	125	126	127	126	126	126
5	107	105	104	102	99	98	99	102	100	98	96	95	95	93	93	93	88	85	82	81	80	79	79	80	78	78	79	79	78	78	80	81	83	81	80	81	82	82	82	83	81	80	80	82	85	89	91	91	91	91	90	89	88	89	92	94	96	96	97	97	97	96	96	95	96	98	97	95	94	94	94	93	91	93	97	101	103	101	100	101	105	105	105	104	102	99	96	95	91	93	90	83	79	79	78	74	79	77	75	75	76	79	80	80	77	75	74	76	78	78	76	74	76	76	75	74	74	75	74	74	74	75	75	75	76	76	74	71	72	72	73	74	74	74	76	79	79	80	80	77	77	78	77	74	73	71	71	73	72	69	70	72	73	74	77	78	80	81	82	83	83	86	85	84	85	85	84	87	86	86	87	88	89	87	85	82	84	85	85	83	82	83	84	84	84	85	86	86	87	89	92	94	100	102	106	108	106	104	104	106	107	106	105	106	107	107	107	107	107	107	108	109	111	112	113	114	114	114	115	117	118	119	123	126	127	127	126	125	125	125	125	123	125	125	126	127	128	127	127	128
6	108	105	103	102	100	99	100	103	99	96	94	94	93	91	90	90	84	82	81	80	78	77	78	81	78	79	79	79	79	79	80	80	81	79	79	80	81	81	82	82	82	83	85	88	90	91	91	91	90	91	91	90	90	91	94	96	95	96	96	96	96	96	96	95	96	96	96	94	92	93	93	93	92	95	100	102	102	99	98	99	102	103	104	103	101	97	94	92	89	89	86	81	79	80	79	77	78	76	74	74	76	78	80	80	78	78	77	77	77	77	76	75	75	75	75	74	73	73	74	75	72	75	77	77	78	78	76	73	74	75	76	77	77	76	78	81	82	84	83	81	80	80	78	74	76	74	74	75	74	71	72	74	73	74	76	79	81	82	82	81	81	84	84	84	85	85	84	86	85	85	86	88	89	89	86	84	85	86	85	83	83	84	84	82	83	84	85	86	87	88	90	91	94	96	101	105	107	106	106	106	107	107	106	106	107	109	109	108	109	109	110	112	114	115	116	117	117	117	118	119	119	120	124	128	126	128	128	126	125	126	125	124	125	125	125	127	128	128	128	129
7	111	107	103	102	101	100	100	101	97	95	93	92	90	88	86	86	82	81	80	79	77	75	76	78	80	79	79	79	79	79	79	78	80	78	78	80	81	81	81	81	85	87	90	91	91	90	90	90	88	90	91	91	91	92	94	97	93	94	94	95	96	97	97	97	97	97	97	94	93	94	95	94	94	97	101	103	100	97	96	98	101	102	103	103	100	97	92	90	89	86	83	82	81	80	80	80	77	75	73	73	75	78	79	79	80	80	80	79	77	76	77	77	72	72	71	70	69	69	71	73	68	71	74	76	76	76	74	72	77	78	80	81	80	79	81	84	84	86	86	83	82	82	80	75	78	75	75	76	75	72	72	75	73	74	76	79	82	83	82	80	79	82	82	82	85	85	83	84	85	85	86	88	90	90	88	86	85	85	84	84	85	87	86	82	83	83	84	85	86	88	90	92	91	91	94	100	105	107	107	108	107	108	107	105	106	109	109	106	107	108	109	111	113	115	116	117	118	118	118	118	118	118	121	125	124	127	128	126	125	126	127	127	124	124	125	127	128	128	128	130
8	107	105	104	105	103	100	99	100	101	96	91	87	86	86	86	86	83	81	79	79	79	78	77	77	75	78	79	79	78	76	77	78	79	78	78	78	80	82	83	84	90	90	91	90	89	88	89	90	91	92	92	93	94	95	96	97	95	94	95	97	98	98	98	99	97	96	95	94	93	93	93	93	96	101	104	101	96	95	96	97	99	100	101	102	102	98	92	87	86	85	82	82	83	85	83	79	75	76	76	74	72	71	74	77	76	76	73	70	69	70	71	70	65	65	65	66	64	62	62	64	65	65	67	68	68	66	67	69	69	70	71	73	74	76	77	78	86	81	78	80	83	83	81	80	78	78	78	77	76	75	75	76	76	75	75	77	81	83	83	82	79	80	81	83	83	82	84	87	85	87	90	90	88	86	86	86	88	88	87	86	85	84	83	82	81	83	85	87	89	89	88	87	91	92	95	96	98	101	105	108	108	108	106	106	108	109	108	106	108	108	108	109	111	113	115	115	118	117	117	118	118	117	119	121	124	126	127	126	126	127	127	126	125	126	128	128	128	128	129	129
9	109	106	105	104	104	103	101	101	98	95	90	86	85	85	84	84	81	80	81	83	83	81	79	79	77	78	80	80	78	77	77	78	82	80	78	78	81	85	88	90	93	91	90	88	88	89	90	90	91	92	93	94	95	96	96	96	96	95	96	98	99	97	97	98	96	95	94	93	93	93	93	94	99	101	101	98	95	95	95	94	98	98	99	98	96	93	91	89	91	89	86	83	83	83	81	78	74	74	74	71	68	68	70	72	73	74	72	70	68	68	67	65	63	62	62	63	62	60	60	61	63	65	68	69	67	65	67	69	68	68	68	68	68	68	69	69	72	70	70	73	75	74	73	72	77	78	78	78	78	77	78	78	80	81	82	83	84	84	83	82	81	81	82	83	83	83	84	87	84	86	87	87	86	86	86	87	87	87	87	86	85	84	83	83	82	83	85	87	89	89	88	87	88	90	92	94	95	98	102	105	106	106	106	104	104	106	107	108	107	108	108	110	113	115	116	116	117	117	118	120	119	118	119	121	122	125	126	126	126	127	127	126	125	125	125	125	125	126	127	128
10	110	108	105	103	103	104	102	100	95	92	88	85	84	84	83	82	79	79	81	83	82	80	78	79	79	80	80	80	78	77	77	77	81	80	78	80	85	90	94	95	95	91	88	86	87	88	89	89	92	92	94	95	96	96	96	96	97	97	98	99	99	98	97	97	95	95	94	94	94	95	95	96	101	100	98	96	95	95	94	92	96	97	98	97	95	93	92	93	90	89	85	80	78	77	75	73	72	72	71	68	65	64	66	68	71	72	72	69	67	66	63	61	63	61	61	61	61	60	60	60	62	65	68	69	67	65	66	69	69	68	67	66	65	64	63	63	63	64	66	69	70	69	67	66	70	71	72	73	74	74	74	75	76	79	82	85	86	87	87	87	84	83	83	84	84	83	84	85	85	85	86	86	85	84	83	83	84	85	86	86	85	83	83	84	83	83	84	87	89	90	88	86	87	88	91	93	94	97	100	102	103	105	105	102	100	100	103	105	105	106	107	109	112	115	116	116	116	116	118	120	120	118	117	118	119	122	124	125	125	126	127	126	125	125	124	123	123	124	126	127
11	107	107	105	102	101	102	100	96	93	90	87	85	84	83	82	80	81	80	80	80	78	76	77	79	81	81	80	79	78	77	77	77	78	78	81	86	91	95	96	96	94	92	89	87	87	89	90	91	94	94	94	95	95	95	96	96	96	98	99	101	100	99	97	97	96	96	96	96	97	97	98	99	100	99	97	96	96	95	93	92	96	96	97	98	95	91	89	89	84	83	79	74	71	71	71	70	71	71	69	67	65	64	66	67	70	72	72	70	68	66	64	62	62	60	60	60	62	62	62	61	64	65	68	69	68	66	67	69	69	67	66	65	64	64	64	63	63	64	66	68	69	68	66	64	64	65	66	68	69	69	70	70	70	72	75	80	84	87	88	88	87	86	86	87	87	86	86	86	85	85	86	86	86	84	82	80	81	83	85	85	84	83	83	84	84	83	83	86	89	89	87	84	86	87	89	91	93	95	97	99	101	104	105	102	99	98	99	99	102	102	103	106	110	113	114	113	113	114	115	117	117	115	115	116	117	119	122	124	125	126	126	126	126	126	125	124	124	124	126	127
12	103	106	105	101	98	97	95	93	91	89	86	85	85	84	82	81	82	82	82	81	80	78	79	81	83	82	80	79	78	78	77	77	80	82	85	91	95	97	96	94	93	93	92	90	90	91	93	94	96	96	95	94	94	94	95	96	96	98	100	101	101	100	99	98	97	97	97	98	98	99	100	100	98	98	99	99	98	95	93	92	95	93	92	92	89	84	80	78	80	79	76	72	69	70	71	71	68	68	67	65	64	65	67	69	70	71	71	69	67	67	66	65	61	60	59	60	62	63	63	62	67	66	67	69	69	68	67	67	66	65	64	63	63	63	63	63	63	63	64	65	68	68	66	63	65	65	66	67	68	69	70	70	70	69	70	73	78	81	82	81	85	86	88	91	92	90	90	91	85	85	86	86	86	86	85	84	80	82	84	84	83	82	83	84	86	85	85	87	89	89	87	84	85	86	87	89	90	92	94	95	98	101	103	103	101	100	98	96	99	99	100	104	108	111	112	111	112	112	113	114	114	113	113	115	115	117	120	122	124	125	126	127	126	127	127	126	125	125	125	126
13	101	103	103	99	95	92	91	91	90	88	86	85	86	85	84	82	81	81	81	83	82	81	80	81	83	81	79	78	79	79	79	79	87	88	90	93	95	95	94	93	90	91	91	91	90	90	92	95	96	96	95	94	94	94	95	96	96	99	101	102	101	101	100	99	98	98	98	99	99	99	100	100	98	99	100	99	96	91	88	88	88	84	83	84	84	80	77	77	79	78	75	70	68	69	70	70	65	65	64	63	63	64	66	68	68	70	70	68	66	67	67	67	63	64	63	63	64	65	66	65	70	67	66	68	69	69	68	67	66	64	63	62	62	63	62	62	62	62	61	62	66	68	67	65	66	65	65	65	66	68	68	68	71	68	66	68	73	77	77	76	79	81	85	88	89	89	90	92	92	91	89	87	85	85	85	85	81	82	84	84	83	83	83	84	87	86	87	88	90	90	88	86	87	87	87	88	89	90	92	93	95	98	100	102	103	104	102	99	99	99	99	102	106	110	111	110	112	112	112	113	113	112	114	116	114	115	118	121	123	124	125	127	127	127	127	126	125	124	124	125
14	100	99	98	95	92	89	89	90	89	87	86	85	86	86	85	84	82	80	80	81	81	81	80	81	82	80	78	78	80	82	83	83	89	91	93	94	94	94	93	93	90	90	89	89	89	91	92	93	94	94	94	95	95	95	95	96	97	100	102	102	101	101	101	100	100	100	100	100	100	100	100	100	100	99	97	95	90	83	79	77	77	76	78	82	83	80	79	80	76	75	72	68	67	68	68	68	64	63	62	61	61	62	64	66	66	68	69	68	66	66	67	67	67	69	68	66	66	67	68	67	71	68	67	67	68	67	67	67	67	65	63	62	63	63	63	62	62	62	63	63	64	67	67	66	66	65	63	63	65	66	67	68	68	66	65	67	72	76	78	77	75	77	81	83	83	82	84	88	93	93	92	91	88	86	85	85	84	84	84	84	84	84	84	85	86	86	87	89	90	90	89	88	89	88	88	87	88	90	92	93	94	96	97	98	100	103	104	103	100	99	99	101	105	109	110	110	112	111	112	113	113	113	115	117	114	114	117	120	122	123	125	128	128	128	127	125	124	123	124	125
15	100	96	92	91	89	87	87	89	89	87	86	85	86	87	86	85	86	83	80	79	80	80	81	82	80	79	77	78	82	85	86	86	86	89	93	95	95	93	93	93	93	91	89	89	91	93	94	94	91	92	94	96	96	96	96	95	98	101	103	102	101	101	101	100	102	102	102	101	101	101	100	100	101	98	94	90	84	76	70	68	72	73	79	84	83	79	76	77	75	74	71	68	67	69	69	68	64	63	62	61	60	61	63	64	65	68	69	68	66	66	66	66	69	70	70	67	65	66	67	67	71	69	68	67	67	66	66	68	66	64	62	62	63	64	63	63	62	64	65	63	63	65	66	65	69	67	65	65	67	69	70	71	67	66	66	68	72	76	78	79	78	79	81	81	79	77	80	85	85	89	93	94	93	90	89	88	86	85	84	84	84	85	85	85	83	84	86	88	89	90	90	89	89	88	86	85	86	88	90	91	94	95	95	94	95	99	103	105	101	99	98	100	105	108	110	110	111	111	112	113	113	113	115	117	115	114	116	119	121	122	125	128	130	129	127	125	123	123	125	126
16	96	92	89	89	89	88	86	86	87	86	84	83	82	83	84	85	84	83	82	80	80	80	82	83	84	78	75	78	83	87	87	86	89	91	93	92	93	94	94	92	92	93	94	96	96	95	93	92	90	92	94	95	95	95	95	95	97	101	102	100	99	101	102	101	105	103	103	103	101	101	101	98	94	89	85	82	77	71	69	71	69	74	79	81	81	80	78	75	73	73	69	64	64	64	64	64	61	63	62	59	58	61	62	60	62	66	70	72	71	68	67	67	69	70	70	69	69	70	70	69	68	68	68	67	66	66	67	68	70	66	64	64	65	64	62	60	61	63	63	61	60	61	62	63	64	65	66	67	67	67	68	68	69	66	64	66	69	73	76	79	76	79	81	81	79	77	77	77	80	82	84	87	88	90	92	94	88	89	89	87	85	83	83	84	86	85	86	88	90	91	90	88	89	86	84	85	86	86	87	89	90	90	90	91	93	96	99	101	103	104	102	100	101	107	111	111	114	114	113	113	113	114	114	115	113	115	117	118	120	123	125	126	129	129	128	125	124	124	124	123
17	94	91	88	88	88	86	86	86	87	85	84	83	84	84	84	84	82	82	81	82	82	83	83	83	81	80	79	83	86	88	89	90	91	93	94	94	94	95	95	94	92	93	93	94	94	93	92	92	91	92	93	94	94	94	95	95	96	99	101	100	102	105	107	105	109	106	106	105	101	99	96	92	89	84	79	77	74	71	71	73	73	76	79	81	82	81	77	74	71	72	67	63	64	63	61	60	59	61	61	59	59	61	61	59	62	66	70	72	71	69	68	68	65	67	68	68	68	68	67	66	66	67	66	66	65	65	66	66	68	64	60	59	59	59	58	58	58	60	60	58	57	58	60	61	65	65	66	67	67	66	65	64	64	62	61	65	69	72	75	77	76	78	80	80	78	77	77	78	81	82	83	83	84	85	87	88	91	91	90	87	85	84	85	86	85	86	87	89	90	90	89	88	89	86	85	85	86	86	86	88	87	87	88	89	91	93	96	97	101	102	103	104	104	106	109	113	113	113	113	113	114	114	114	114	114	115	117	118	120	122	125	126	128	129	128	126	125	125	125	125
18	92	90	88	87	86	85	85	86	86	84	83	83	84	85	83	82	82	82	82	83	84	85	83	82	80	82	85	88	90	90	92	94	95	96	96	96	96	97	97	95	93	93	93	93	93	93	93	92	92	92	92	92	92	93	94	95	97	100	102	103	106	110	110	109	109	106	104	101	95	91	89	85	82	78	74	73	73	72	72	73	74	76	78	79	80	80	76	73	73	73	69	65	66	65	61	59	57	59	60	59	59	61	60	58	63	67	71	72	71	70	69	69	65	66	65	65	65	66	66	65	64	64	64	63	63	63	64	64	67	62	58	56	56	55	55	55	56	57	57	55	55	56	58	59	64	64	66	67	67	66	63	60	60	59	60	65	69	72	74	75	74	75	76	76	75	75	76	77	82	82	82	81	81	81	82	83	85	88	91	92	90	88	86	85	85	86	88	88	88	88	88	88	88	86	85	86	86	86	86	87	86	86	86	88	89	91	93	94	98	99	103	107	106	104	107	113	111	112	113	114	114	114	114	114	115	115	116	117	119	121	124	126	128	129	129	127	126	126	127	126
19	91	90	89	87	86	85	85	86	86	84	82	82	84	84	83	81	83	82	83	83	83	83	82	80	82	84	88	91	92	92	93	95	97	97	96	97	97	97	97	96	93	93	93	93	94	93	93	93	93	92	91	90	90	92	94	96	100	102	104	106	109	111	110	107	106	101	98	93	87	84	83	80	75	73	71	73	74	73	71	70	72	73	75	77	77	77	75	74	77	75	70	67	68	66	61	60	56	58	59	58	59	60	60	58	64	68	72	72	71	71	70	70	68	68	66	64	64	66	67	67	63	63	62	62	62	62	62	63	65	62	59	59	58	56	54	53	55	56	56	54	54	56	58	58	63	63	64	66	67	65	62	59	60	60	61	65	69	72	73	73	73	73	74	73	73	74	75	77	79	79	80	80	80	79	79	79	78	82	86	90	90	88	87	86	86	87	88	87	86	85	86	87	87	86	86	86	87	86	86	85	86	86	87	88	89	91	92	92	95	97	102	106	106	106	108	112	110	111	112	114	114	114	114	113	116	115	116	117	118	120	123	126	127	129	130	128	127	127	127	126
20	91	91	89	87	85	84	85	85	86	83	81	80	82	83	82	81	82	82	82	82	81	81	82	82	87	87	89	92	92	92	93	95	96	95	95	96	97	97	96	95	91	92	93	94	94	94	93	93	92	91	90	90	91	94	96	98	101	103	106	108	110	110	107	104	102	98	95	90	83	80	78	75	70	68	68	70	72	72	71	70	71	73	75	76	75	74	75	76	76	74	68	66	67	64	60	60	57	58	58	57	58	59	60	60	64	69	72	72	71	70	70	70	69	69	68	66	66	67	67	66	64	63	62	61	61	61	62	62	64	62	60	60	59	57	54	54	55	56	55	54	54	56	58	58	64	64	64	64	64	63	61	59	60	60	61	64	68	72	73	74	73	73	73	73	74	75	77	79	77	78	79	80	80	79	77	76	77	78	79	80	81	83	88	91	90	91	90	87	84	83	84	86	86	86	86	86	87	87	86	85	86	86	87	88	89	90	91	91	94	98	101	102	105	109	111	111	110	111	112	113	114	114	114	114	116	115	115	117	118	119	122	125	126	129	130	128	127	126	126	125
21	90	90	88	85	84	85	84	84	86	84	81	80	82	83	82	81	80	80	80	81	82	84	86	86	91	90	90	92	93	92	92	93	95	94	94	96	98	97	96	95	91	92	93	94	94	93	92	92	90	89	89	90	93	96	99	101	100	102	104	107	108	107	105	103	98	95	93	89	81	75	72	68	66	64	63	65	68	71	73	74	74	76	77	77	75	73	74	77	75	72	67	65	66	63	60	60	59	58	57	57	57	59	61	62	65	69	72	71	69	69	69	68	67	68	69	69	69	69	66	63	64	63	62	62	61	61	61	61	63	61	58	58	57	56	55	55	55	56	55	53	54	56	58	58	66	65	64	63	61	59	58	57	58	59	59	61	66	71	74	74	72	72	72	72	73	75	77	78	80	80	82	83	82	80	77	75	75	75	76	76	77	79	83	86	92	93	92	89	85	83	84	85	85	86	86	85	86	87	87	85	86	86	87	87	88	89	90	91	94	98	100	101	104	110	113	112	111	111	111	112	113	114	114	115	117	115	115	117	118	118	120	124	126	129	131	129	127	126	125	125
22	90	89	87	85	85	87	86	84	85	84	83	82	83	83	82	82	81	79	78	81	86	90	90	89	92	92	93	94	93	92	92	93	94	93	94	97	99	98	96	96	94	94	94	94	93	92	92	91	91	91	91	92	95	97	99	100	99	100	102	103	104	103	102	102	97	93	91	85	76	70	67	64	63	63	63	64	66	70	74	76	76	76	76	76	73	71	73	75	72	70	67	66	66	63	60	61	60	59	58	57	58	59	61	63	65	70	72	70	68	68	68	66	67	67	68	69	70	70	67	63	66	64	63	62	62	62	61	60	61	59	58	59	58	57	56	56	56	56	55	53	54	56	58	58	64	65	65	63	59	57	56	56	57	58	59	61	65	71	73	72	69	69	69	70	71	73	75	77	81	82	82	83	83	81	78	75	71	73	76	78	78	78	79	80	87	88	89	89	87	86	85	85	84	85	85	85	86	87	87	85	86	86	86	87	88	89	90	91	92	95	98	100	103	107	111	113	113	112	111	111	112	113	115	116	117	115	115	118	118	117	119	123	125	129	131	130	128	127	127	126
23	90	89	87	85	86	89	88	86	84	84	84	84	84	83	83	82	83	79	78	82	90	95	93	90	91	93	95	96	94	91	91	93	94	93	94	98	101	99	97	97	97	96	95	94	93	92	92	92	94	93	93	94	95	97	98	97	99	100	101	101	100	99	101	102	99	94	89	81	72	68	68	66	61	63	65	66	68	71	74	75	75	73	72	72	72	70	71	73	68	68	66	66	66	62	58	60	60	59	59	59	59	60	61	63	66	70	72	69	67	67	67	65	68	68	67	66	68	69	69	67	66	65	63	62	62	62	61	60	58	58	60	62	62	59	57	56	57	57	56	54	54	57	58	58	62	63	64	62	59	56	55	56	57	59	60	62	66	70	71	70	69	69	69	70	72	74	76	77	79	79	79	80	80	79	76	75	73	74	76	76	76	77	79	81	79	82	85	88	89	88	87	86	84	85	85	84	85	88	88	86	86	86	86	87	88	89	91	91	89	91	95	101	102	103	107	113	114	113	111	110	111	113	115	117	116	115	116	118	119	117	118	122	125	129	132	131	129	129	128	128
24	91	89	88	88	90	90	88	86	86	86	85	85	85	84	82	81	80	81	84	89	92	93	91	89	91	92	93	92	90	90	92	95	94	95	96	96	96	96	97	98	97	96	96	96	94	92	92	94	94	96	97	97	97	99	99	97	99	100	99	96	95	97	98	97	97	91	84	76	71	68	66	65	63	64	65	67	68	70	71	72	71	73	73	72	72	73	73	72	65	66	66	66	65	64	61	58	58	60	60	58	57	60	62	64	66	71	73	70	67	67	66	64	65	64	65	68	70	70	68	67	65	63	62	63	63	60	58	57	57	59	63	65	63	59	56	56	57	56	55	55	57	58	58	58	64	61	60	61	61	58	56	57	58	62	62	65	71	70	67	71	71	72	71	70	71	74	77	78	79	77	76	76	77	78	76	75	71	75	75	74	77	79	79	79	81	81	80	78	79	84	89	91	84	86	87	86	86	88	89	88	86	87	89	89	89	89	90	90	89	93	97	99	100	103	108	112	113	113	112	110	110	111	114	117	116	116	117	118	119	120	120	121	123	128	132	132	131	130	129	128
25	90	90	89	88	88	88	88	88	88	87	86	85	85	84	83	82	84	86	89	91	93	92	90	88	91	91	91	91	90	91	92	93	92	93	94	95	95	95	95	95	97	97	97	96	95	94	94	94	97	99	99	98	97	97	97	97	96	97	96	94	94	96	96	95	94	89	82	76	71	68	67	66	66	66	66	67	68	69	70	71	71	73	74	73	73	72	71	69	64	66	67	65	63	61	59	58	57	60	61	59	56	58	61	64	67	72	74	72	69	68	67	64	64	63	64	67	69	68	67	66	65	62	60	61	61	60	58	58	56	58	62	65	64	61	58	57	56	56	56	56	57	58	58	58	62	60	59	61	61	58	56	58	58	62	62	65	71	69	67	71	72	73	72	71	72	74	76	75	75	74	73	74	75	75	74	72	71	74	74	73	76	77	78	80	81	80	76	72	72	77	82	85	88	87	85	85	88	91	90	86	86	87	89	89	88	88	88	89	89	92	95	97	99	102	106	110	113	113	114	113	112	111	112	114	116	116	117	119	120	121	121	122	122	126	131	132	131	131	130	129
26	91	91	90	89	87	88	89	90	89	88	86	85	85	85	85	84	89	91	94	95	94	92	90	89	92	91	90	89	90	91	92	92	92	93	94	95	94	94	94	94	97	98	98	96	96	98	97	95	98	99	98	96	95	95	96	96	94	94	93	93	94	95	94	92	88	85	79	74	70	68	67	66	69	68	67	67	68	70	70	70	71	73	74	74	73	71	68	65	63	66	67	64	60	58	58	57	57	60	62	59	56	56	60	63	67	72	74	72	70	68	66	63	64	63	64	66	68	68	67	66	65	61	59	59	59	59	59	59	56	57	60	64	65	62	59	58	55	55	57	57	57	58	58	59	60	58	58	61	61	59	57	58	58	61	63	66	70	69	68	71	73	73	73	72	72	73	73	73	74	73	72	72	73	74	74	73	71	73	72	72	73	73	76	81	82	81	77	73	71	73	76	78	84	86	89	89	88	88	88	88	87	88	89	89	89	88	88	88	89	90	92	95	97	101	104	106	110	112	115	116	115	113	112	112	116	117	118	120	121	122	122	123	120	125	129	131	132	132	131	129
27	93	92	90	89	88	89	90	92	89	88	87	86	86	87	88	89	91	94	97	97	95	93	92	92	93	91	90	89	89	90	90	90	93	94	95	96	95	94	94	94	97	99	99	97	98	100	99	95	95	94	92	92	92	94	95	95	94	93	91	92	93	93	91	89	85	83	79	75	71	69	68	68	70	69	67	67	68	70	71	70	70	71	72	72	71	70	67	64	64	66	66	64	61	59	59	58	58	60	61	60	57	56	59	62	66	70	73	72	69	67	64	61	63	62	63	65	67	66	65	65	64	61	59	59	60	59	59	60	58	57	58	61	63	62	59	58	54	56	57	58	58	58	59	59	59	58	58	60	61	60	59	59	58	60	63	67	69	69	69	71	72	71	70	69	69	70	71	71	74	72	70	69	70	72	74	75	70	71	70	71	71	70	73	81	81	81	79	77	75	74	74	74	76	81	87	90	90	89	88	88	88	88	89	89	89	89	88	88	88	89	90	93	96	100	103	104	105	109	113	115	116	115	115	115	116	117	118	120	121	122	123	123	121	124	128	131	132	132	131	129
28	94	92	89	88	89	90	91	90	89	88	88	87	88	90	92	93	93	96	98	98	95	93	93	93	93	92	91	89	87	87	88	89	93	94	95	96	96	95	95	95	98	100	100	98	98	100	98	93	93	90	87	88	91	93	93	92	92	91	89	90	90	89	86	84	84	83	80	77	74	72	71	70	72	70	68	68	68	69	70	69	69	70	70	69	69	69	68	65	66	66	66	64	63	63	61	59	60	60	60	60	59	58	59	61	66	70	72	72	70	66	63	61	62	61	62	64	65	64	64	64	63	61	59	60	61	60	59	59	59	57	56	58	60	60	59	58	54	56	58	58	58	58	59	59	58	57	57	59	61	61	61	61	58	59	63	67	68	69	70	71	71	68	66	65	66	67	69	69	68	68	68	68	68	69	70	71	70	70	69	69	70	68	71	78	77	77	77	76	74	72	72	72	76	75	78	85	92	95	91	87	87	87	87	88	88	89	89	89	88	88	89	91	95	99	101	102	102	105	109	112	114	115	116	117	117	117	118	119	120	121	122	122	122	124	127	131	132	132	130	129
29	93	90	88	88	89	90	89	88	88	89	89	90	91	93	95	97	96	98	98	97	94	92	92	93	92	91	90	88	86	86	87	88	92	93	94	94	95	95	95	96	99	101	101	99	98	98	95	92	92	89	86	88	91	92	91	90	90	88	87	86	86	83	81	80	81	81	80	77	75	73	71	71	73	72	71	69	68	68	68	68	69	69	68	67	68	69	68	67	67	67	67	66	65	65	63	60	60	60	59	60	61	60	60	61	68	70	73	73	71	67	64	62	64	63	64	66	66	65	64	65	63	61	61	62	62	61	59	58	59	56	55	57	59	59	58	58	56	57	58	58	58	58	59	59	57	56	57	58	60	61	62	62	59	58	63	68	67	67	70	69	69	65	63	62	63	65	67	68	63	66	68	69	69	68	68	68	69	70	69	68	69	68	70	75	75	74	73	72	71	71	72	74	75	74	75	80	86	90	92	93	87	86	86	86	87	89	89	90	88	88	89	91	93	97	99	101	101	104	107	109	111	113	116	118	119	118	118	119	119	120	121	122	123	123	126	130	132	131	130	129
30	91	90	90	90	90	90	89	88	89	90	92	93	94	96	97	98	98	98	97	95	93	92	92	93	91	90	88	86	86	87	88	88	91	92	92	93	93	94	96	97	100	101	102	101	98	95	92	90	90	88	88	90	91	91	90	90	88	86	85	84	83	80	78	78	79	79	79	78	75	73	72	72	73	73	73	71	69	67	67	68	69	69	68	67	68	70	69	67	66	68	68	67	65	64	62	60	59	59	60	61	61	60	60	62	69	70	72	73	71	68	65	63	65	65	65	66	66	65	64	65	64	62	61	62	62	60	58	57	56	55	55	57	59	58	57	57	58	57	57	57	58	59	59	59	56	56	55	56	58	61	62	63	60	59	65	68	65	65	68	67	67	64	61	62	63	64	65	66	64	67	69	70	69	68	68	69	68	71	70	68	69	69	69	71	75	73	73	73	72	71	72	75	72	74	77	78	78	80	87	94	88	87	86	85	87	89	90	91	89	89	90	90	92	94	97	98	100	102	105	107	109	112	115	118	121	121	120	119	119	120	121	122	124	123	124	128	131	131	130	130
31	90	91	92	92	91	90	89	89	89	91	94	95	96	97	98	99	98	98	96	94	93	93	94	95	91	88	85	85	87	89	89	88	90	91	92	92	93	94	96	98	101	101	102	101	97	92	89	89	86	86	88	91	91	89	90	92	87	86	84	84	81	78	78	79	79	80	81	80	78	76	76	75	72	73	74	72	69	68	69	70	69	69	68	68	69	70	69	67	65	68	69	67	64	62	60	59	57	58	60	62	60	59	60	64	69	70	72	72	71	67	65	63	64	63	64	65	64	62	62	63	65	62	61	61	61	60	58	57	54	54	56	58	59	58	57	57	59	58	57	57	58	59	59	59	56	55	54	55	57	60	62	63	62	60	65	69	64	64	66	64	67	63	61	62	64	64	64	65	66	68	69	68	67	67	69	71	68	71	70	68	69	70	69	68	73	72	73	74	73	71	71	72	73	73	73	75	76	77	82	87	91	89	87	86	88	90	91	92	90	91	91	90	91	92	94	96	99	101	103	106	108	112	116	119	124	122	121	120	119	120	122	123	124	122	123	128	131	131	131	131
32	94	93	94	95	94	91	89	89	94	95	97	99	99	99	98	97	97	96	95	95	95	95	94	93	92	91	89	87	87	87	88	89	87	88	89	91	92	94	96	98	103	102	101	98	94	90	86	85	84	87	91	91	87	88	91	91	82	85	85	79	76	76	77	77	82	82	82	81	80	79	79	79	75	73	73	75	74	69	67	68	69	67	67	66	66	69	70	65	67	69	68	68	66	60	59	63	61	61	62	62	61	61	62	63	68	69	71	72	71	68	65	63	61	62	64	63	62	61	61	62	61	62	62	62	62	63	61	58	56	56	55	55	58	61	59	56	60	59	59	59	59	58	58	58	56	55	54	55	58	59	59	59	60	63	65	64	63	63	64	64	63	60	60	64	65	63	63	64	67	68	68	67	67	69	70	69	69	70	69	69	69	71	72	71	75	71	70	73	74	72	71	72	70	70	73	75	76	75	77	79	86	89	91	88	88	91	93	92	91	92	93	92	92	93	96	99	98	98	99	101	105	110	115	118	119	121	122	123	123	122	122	122	122	122	124	127	130	130	131	131
33	94	94	95	96	95	92	92	93	98	99	100	102	102	101	99	97	97	96	95	95	94	93	91	89	91	89	88	88	89	90	90	90	88	89	91	93	94	95	97	98	100	101	100	96	91	87	86	86	87	87	89	88	86	87	89	87	80	82	80	75	72	74	76	75	80	81	82	82	81	80	80	80	78	76	75	75	73	69	68	69	69	67	67	65	64	67	69	67	65	66	66	65	65	62	60	61	61	62	62	62	62	62	64	65	68	70	72	72	70	67	64	62	60	61	61	60	58	58	59	61	61	61	62	61	62	62	61	59	57	56	55	55	57	60	59	57	58	59	59	59	59	58	57	57	54	54	54	56	58	60	61	60	59	62	64	63	63	63	63	62	64	61	61	64	65	63	63	64	68	69	68	67	68	70	71	71	70	70	70	68	69	71	72	73	74	71	70	73	74	72	71	71	72	72	73	76	76	75	76	78	81	86	90	91	92	93	92	88	91	92	93	93	92	93	94	96	98	98	98	100	103	107	111	114	117	119	122	123	122	121	122	122	123	122	123	126	128	129	129	130
34	93	93	94	94	93	92	94	97	100	101	102	103	104	102	99	97	97	96	96	95	94	92	89	87	88	87	87	88	91	92	92	91	89	90	93	94	96	97	98	99	99	99	98	94	88	86	86	88	90	88	87	86	84	86	86	82	81	80	77	72	72	75	77	77	77	80	82	83	82	81	81	81	80	77	74	73	71	68	67	69	68	67	66	64	62	64	68	68	63	65	64	63	66	65	61	60	62	62	62	62	63	64	66	67	69	70	72	72	69	66	63	61	59	59	58	57	56	56	58	60	60	61	61	61	61	62	61	59	59	58	56	55	57	60	60	59	58	58	59	59	58	57	56	55	55	54	55	56	59	61	61	60	59	61	63	63	63	63	62	61	65	63	62	64	64	63	63	64	69	68	67	67	68	71	72	71	70	71	70	68	68	70	72	73	72	70	70	73	75	73	72	72	75	75	75	76	76	75	75	76	77	82	87	90	93	95	92	88	92	92	93	93	94	94	94	95	98	98	98	99	102	105	108	110	113	116	120	123	123	122	122	123	124	123	123	125	127	128	128	130
35	90	90	90	89	89	91	96	100	102	102	102	103	104	103	101	99	98	97	96	95	94	93	91	89	85	85	85	88	91	93	92	90	89	91	93	95	96	97	98	99	99	98	96	92	89	87	88	90	90	88	86	85	83	84	82	78	81	79	75	72	73	76	78	78	77	80	83	83	82	81	81	82	83	79	75	73	72	70	69	71	70	67	66	64	62	64	67	67	61	65	65	64	66	66	63	61	62	62	63	64	65	65	66	67	69	71	73	72	69	64	61	59	58	58	57	56	56	57	59	60	59	60	60	60	60	60	60	58	59	59	58	58	59	62	62	61	60	59	58	57	56	56	55	55	56	56	56	58	60	60	60	58	58	61	63	63	63	63	62	60	65	63	62	64	64	63	63	64	68	67	66	65	67	71	72	71	70	72	72	70	68	69	71	72	70	69	70	74	76	75	74	74	78	78	77	76	76	75	75	75	77	79	82	85	90	94	95	94	93	93	93	94	95	96	96	96	99	99	99	100	102	104	107	108	110	113	117	121	124	125	124	124	124	123	123	125	126	127	128	130
36	89	89	87	85	85	90	96	101	104	102	102	103	104	105	105	104	100	98	96	94	93	92	92	91	84	84	85	87	90	91	90	88	90	92	94	96	97	98	98	99	99	96	93	91	90	90	90	89	88	87	87	85	81	81	80	75	77	76	73	72	73	76	77	77	79	81	83	84	83	82	82	83	85	82	78	77	76	75	75	76	72	67	65	65	63	65	66	64	61	66	66	64	65	65	63	62	62	63	64	66	67	67	67	66	71	72	74	72	68	63	60	58	56	56	57	58	58	58	59	60	59	60	60	59	58	59	59	58	57	58	59	59	61	62	62	61	62	60	58	55	54	54	54	55	55	55	56	58	60	60	59	58	58	61	63	63	63	63	62	60	64	63	63	64	64	64	64	65	66	66	65	65	67	70	72	71	71	73	73	72	71	71	71	70	70	69	70	74	77	78	78	78	80	79	78	77	76	75	75	75	77	77	78	80	86	92	97	98	98	97	96	95	96	97	98	98	98	98	99	100	102	104	106	107	108	110	113	119	124	127	127	125	124	122	122	124	126	127	128	129
37	90	89	86	84	85	91	98	101	101	100	98	99	102	105	106	105	102	99	96	93	92	91	91	90	85	85	86	88	89	90	89	89	93	94	95	96	96	96	97	97	96	93	91	90	92	92	90	88	85	85	85	83	79	78	78	75	75	74	72	72	74	76	77	77	80	82	84	85	85	84	83	83	83	82	80	79	79	79	78	77	73	67	65	65	64	65	66	64	61	65	65	64	65	64	63	64	63	64	66	68	69	70	69	68	72	74	75	73	68	62	58	57	54	55	57	58	59	59	58	58	58	59	59	58	57	58	58	58	56	58	60	60	60	61	61	60	62	60	56	53	52	52	54	55	53	54	55	58	60	61	59	58	58	61	63	63	62	62	62	61	63	64	65	65	65	65	65	66	66	67	66	66	67	70	72	72	72	73	74	73	73	73	71	69	70	69	69	72	76	79	81	81	80	80	78	76	76	76	76	75	75	75	76	78	83	90	95	97	102	101	99	98	97	97	97	98	98	98	99	101	102	104	105	106	108	108	111	116	123	127	128	127	124	122	122	123	125	126	127	128
38	90	89	87	86	88	94	99	100	98	96	95	97	100	103	104	104	101	99	96	94	92	92	91	90	88	88	89	89	89	90	91	92	95	95	95	95	93	93	93	93	92	91	91	92	93	92	90	87	84	82	81	79	76	77	78	75	75	74	73	73	74	76	78	80	80	82	85	88	89	87	84	82	81	80	80	81	81	81	79	77	72	67	64	64	63	64	66	66	63	64	63	64	66	65	64	66	66	66	67	69	71	73	74	74	73	75	76	73	68	61	58	56	55	56	57	58	58	58	57	56	56	58	58	57	57	58	59	59	58	60	61	60	60	60	60	59	60	58	55	52	51	52	53	54	52	53	55	57	60	60	58	57	57	61	63	62	60	60	61	62	64	66	67	67	66	66	66	65	65	67	68	67	67	69	72	72	71	71	71	71	72	73	72	69	71	69	68	70	74	78	81	82	79	79	77	75	75	76	76	75	75	75	75	77	81	85	91	94	102	102	101	99	98	97	98	99	99	99	100	102	103	105	105	106	107	108	111	115	120	124	127	128	125	124	123	125	126	125	126	127
39	89	89	88	87	91	96	98	98	96	95	95	97	101	104	104	103	99	98	96	95	94	94	93	92	90	91	91	91	90	91	93	94	96	95	94	93	91	89	89	89	89	91	92	94	94	93	90	88	84	80	78	75	73	76	78	76	75	74	72	72	73	75	78	80	79	81	85	90	92	90	86	82	81	81	82	83	84	83	80	77	71	66	64	64	61	62	67	69	66	64	62	64	69	68	66	68	68	67	67	69	72	75	77	78	74	76	77	74	67	61	57	56	57	58	58	58	58	57	56	56	55	56	57	56	56	58	60	60	62	63	63	61	59	60	60	60	57	55	53	52	51	52	53	54	53	54	55	58	59	59	57	55	56	60	63	62	59	59	61	62	65	67	69	69	68	67	66	65	63	66	68	67	67	68	71	72	69	68	67	67	70	72	71	69	71	69	68	68	72	77	80	82	78	78	76	74	74	76	77	75	75	75	75	76	78	82	88	92	98	100	101	100	99	98	99	100	101	101	102	104	105	106	106	106	107	109	112	115	117	121	126	129	128	126	125	127	127	126	126	126